package com.yb.project.algorithm.graph;

import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;


/**
 * leecode 1584. 连接所有点的最小费用
 * @author fxb20
 * 
 * 	给你一个points数组，表示 2D 平面上的一些点，其中points[i] = [xi, yi]。
 * 连接点[xi, yi] 和点[xj, yj]的费用为它们之间的
 * 曼哈顿距离：|xi - xj| + |yi - yj|，其中|val|表示val的绝对值。
 * 请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有一条简单路径时，才认为所有点都已连接。
 *
 */
public class YbMinCostConnectPoints {
	
	public static void main(String[] args) {
		//int[][] points=new int[][] {{0,0},{2,2},{3,10},{5,2},{7,0}};
		int[][] points=new int[][] {{-8988,-8416},{-5299,7210},{-5132,-6801},{-501,4378},{-6429,-2747},{-6707,7699},{4136,-6086},{6311,-5534},{-4114,-9305},{-8189,-9624},{9644,-4646},{-8520,3180},{9018,-2556},{-5445,4930},{1549,7421},{-455,-7400},{3578,1030},{-9676,-7740},{6823,-2933},{8599,1252},{-9122,6121},{-4331,-5318},{8399,4967},{1454,-7459},{-8826,-6339},{-1601,-6797},{-9473,247},{1092,-4900},{5946,-2760},{-4227,9007},{-2034,-1698},{1647,7561},{1353,-9845},{8132,9102},{8012,6644},{8496,-4241},{-4084,1708},{2145,-5993},{4171,7629},{3700,8578},{-4532,9034},{1504,-8983},{-2943,-2501},{9505,-8352},{2729,3954},{-1834,-1837},{-1083,-7265},{5475,-1753},{2684,589},{1269,-4238},{-2160,9037},{-5638,6135},{5638,2211},{5235,8446},{-3559,-3221},{372,9599},{1091,3439},{-1939,2607},{7559,7687},{2411,-9285},{774,6395},{8933,-4090},{1729,-7803},{7707,221},{192,6442},{2666,-8556},{-9394,-7278},{-3436,6198},{-6875,-5577},{-2867,-8426},{-8793,-3110},{-7341,-169},{5555,-1718},{-9725,-4156},{-2756,7213},{1413,-6421},{3261,2341},{-4749,9258},{-8220,1700},{-8242,6550},{6618,-1170},{6851,8241},{5619,3580},{-8944,1442},{-990,9490},{9526,2764},{2867,9679},{-1257,-8846},{-2790,7544},{-8419,-4198},{-3594,4537},{7874,-1396},{3646,-7597},{7350,2628},{9478,-2709},{-4623,-5005},{9044,-3746},{-6955,-5785},{-2175,5650},{4367,-3521},{8504,-1616},{-4546,-2365},{8841,5989},{-5191,1178},{9692,125},{-593,1298},{8350,-2744},{-603,9710},{8983,-3423},{-6393,-1619},{5439,-2874},{4686,-9336},{8776,4842},{-1654,-2478},{-1325,107},{-2511,-7791},{-8477,-5472},{-7026,-427},{-2426,-5032},{2,7761},{3937,-4022},{5355,9532},{337,-2619},{-2166,-4865},{-314,-2231},{-6403,-356},{8370,3473},{-4575,1726},{-3380,-7740},{-8538,3338},{-9502,-1065},{-6139,8975},{-5613,-3139},{-739,-4537},{-5365,329},{7868,3052},{-6290,7374},{-8647,5963},{9889,-2064},{9974,-4514},{5313,-7159},{-7519,1076},{7748,-3701},{-8180,3306},{9686,2669},{9247,-5331},{7282,-7061},{-3077,9371},{-3418,3846},{5637,4391},{-4230,-121},{5453,9099},{1959,6109},{5093,-8844},{5054,8312},{3659,-940},{8363,9969},{-101,-264},{-11,5271},{9460,5886},{494,-4020},{-8877,8164},{-2303,-5103},{-7535,-6647},{-5321,8877},{-5981,6099},{5451,2469},{-1469,-7877},{-5688,-9714},{8648,-7318},{-4535,6785},{2974,5314},{-6017,-5672},{6821,1176},{5458,3798},{-2684,6453},{813,8999},{-6524,8952},{-4414,6571},{3109,-9498},{-3787,5517},{1510,-7545},{5376,8396},{4069,7141},{-562,397},{7604,-6051},{7237,-9629},{-1970,5925},{-9338,-8166},{-6285,7404},{7655,8779},{-5772,-101},{6310,6307},{-4812,2604},{7992,7534},{1100,-1035},{1318,-8732},{8995,-9691},{-8415,-7895},{-5136,-6000},{-3625,-330},{1030,-4247},{2787,1385},{-624,-7305},{-1976,-2812},{-741,-9974},{-6193,-4721},{1199,157},{8295,9380},{-5658,-5301},{-6675,-4990},{-2181,-701},{5192,408},{-1692,6007},{-3271,-8525},{6862,-9175},{-2055,1786},{5905,-486},{3032,1347},{1581,4776},{-4249,-949},{2943,3646},{-8158,1645},{-7362,2848},{3488,-3259},{3483,-7734},{-1535,-8670},{-5878,-7635},{-5536,3947},{-2244,658},{5875,4050},{7989,-1189},{8642,7381},{-6640,-8838},{4971,-2124},{-6951,-8377},{-452,-8449},{1789,-3908},{-8879,-3281},{8668,-1666},{2412,3345},{-4813,5466},{6476,361},{6271,4086},{-1623,-3600},{-5234,-7773},{3992,7081},{5964,7402},{-5158,-307},{-9346,5117},{-2788,1219},{-9691,-7467},{3983,-3384},{9258,-5179},{7457,-3511},{8945,-603},{-3818,-9181},{7617,-6696},{2759,3932},{1528,-8928},{7434,-3165},{-1069,-4960},{3207,-5549},{-6276,-1351},{3744,-9299},{-6972,3162},{-6886,-2824},{-9271,7476},{-1595,1728},{-29,-1217},{7249,8212},{1146,-6591},{1784,6986},{-1585,1461},{-6850,1592},{2703,-8838},{-7391,2755},{-5065,-5565},{-4756,7472},{-3846,4104},{-5041,-1126},{-4896,-9019},{-3624,6080},{4077,-1332},{8627,-5382},{-5786,9566},{-4567,4490},{2253,-6215},{-579,-9047},{-647,-1579},{-2278,-7088},{6855,-3423},{6192,6193},{-3962,-3285},{-785,6981},{6796,2665},{6749,-2647},{7149,840},{7234,2152},{559,-2138},{6132,-4945},{-8386,1981},{-4861,413},{2423,-1170},{7790,-831},{-7736,3443},{-2634,4789},{860,365},{3460,-6434},{-1297,-2600},{-6190,-8501},{-7956,9131},{-3060,-4059},{-9644,7930},{-2873,6790},{5874,-6554},{-9417,-1207},{-456,4639},{-4566,9926},{-9438,2825},{-6042,-3183},{-6495,-3877},{7744,-6847},{-7017,7854},{1848,6927},{-4389,1563},{-4795,6535},{-5241,4654},{6237,-3216},{7194,-2613},{-4326,-5007},{-9698,-778},{6241,5525},{6461,6649},{-8533,5329},{1165,6283},{-4292,-7563},{7594,3596},{-3525,-750},{2025,-4290},{2056,3713},{-1580,-2},{-3026,-4448},{913,1398},{1784,9855},{6823,5176},{-4101,-7117},{9378,-820},{5188,-7520},{6441,-5630},{9220,-2304},{-700,-5775},{-1778,-8855},{-5798,-4711},{1363,-5175},{9020,4459},{326,7169},{6069,2083},{-1523,1319},{-5172,-1917},{9427,8576},{-8713,-5436},{6950,2613},{7137,-7896},{5799,-4602},{6194,1863},{1324,3743},{-9168,-6443},{1465,-1789},{-65,-5349},{-6439,-1075},{-7931,7102},{3888,-4675},{1411,-9841},{-6485,-9322},{9441,-8060},{4728,6773},{-9411,1317},{6466,3161},{1892,-5184},{-8238,-4791},{2143,5460},{4833,1765},{-98,-8624},{-6431,1285},{7949,-6954},{-2162,1485},{-6691,-4410},{6405,6575},{7663,-6223},{-9712,3091},{977,4378},{-4846,6846},{1136,-2407},{-9413,8690},{8173,-8524},{-2463,-8684},{5856,-527},{-9484,5483},{5568,2532},{-3325,640},{-6906,8347},{8943,1320},{1972,9204},{9670,6174},{-2539,8811},{8071,-2298},{4322,9261},{-824,-640},{667,-7559},{2935,3765},{961,1933},{-4225,554},{-2672,-3510},{5510,-4440},{4814,-6211},{5334,115},{4862,3075},{-1938,-7453},{5563,8333},{4903,4369},{-1962,-6210},{-4275,-2512},{-6366,-3346},{9252,5797},{7291,1919},{-8155,-9318},{9531,-3092},{-8120,7513},{-8421,306},{3297,-3803},{9593,-9650},{8578,4628},{5431,3966},{-9600,675},{4979,-5283},{1616,215},{-252,-733},{1846,102},{-4586,3178},{-7218,-2268},{-252,4357},{6752,9575},{4045,7027},{2872,145},{-2515,8818},{7343,7036},{-9071,-8979},{1567,-8532},{5710,4639},{-7649,-4757},{-2316,-3250},{-740,-8523},{-8934,-6745},{9941,2407},{1952,-7321},{4152,-448},{-9594,1085},{-2192,-7473},{9257,4488},{8369,-1238},{-3452,-8993},{-6954,5505},{-312,4659},{-7728,6193},{8092,-6396},{-909,5334},{4077,9062},{-2916,-2665},{-9831,7040},{-9131,2894},{-1036,-8186},{-4364,-5071},{-5484,1140},{-9514,6979},{-6770,5050},{-9931,6683},{-2080,5690},{-4430,-5829},{8014,-7985},{5821,-8714},{5457,9374},{-7217,5224}};
		
		YbMinCostConnectPoints yb=new YbMinCostConnectPoints();
		int result=yb.minCostConnectPoints(points);
		System.out.println(result);
		
	}
	
    public int minCostConnectPoints(int[][] points) {
    	long time=System.currentTimeMillis();
    	int l=points.length;
    	LinkedList<Edge> list=new LinkedList<Edge>();
    	for(int i=0;i<l;i++) {
    		for(int j=i+1;j<l;j++) {
    			int len=Math.abs(points[i][0]-points[j][0])+Math.abs(points[i][1]-points[j][1]);
    			Edge edge=new Edge(len, i, j);
    			list.add(edge);
    		}
    	}
    	System.out.println("cost插入:"+(System.currentTimeMillis()-time));
    	if(list.size()==1) {
    		return list.get(0).len;
    	}
    	
//    	Collections.sort(list, new Comparator<Edge>() {
//            public int compare(Edge e1, Edge e2) {
//                return e1.len - e2.len;
//            }
//        });

    	
    	list.sort(new Comparator<Edge>() {
			@Override
			public int compare(Edge o1, Edge o2) {
				
				 return o1.len - o2.len;
			}
		});
    	System.out.println("cost排序:"+(System.currentTimeMillis()-time));
    	int[] parent=new int[l];
    	for(int i=0;i<parent.length;i++) {
    		parent[i]=i;
    	}
    	int result=0;
    	Iterator<Edge> iterator=list.iterator();
    	while(iterator.hasNext()) {
    		Edge edge=iterator.next();
    		if(union(parent, edge.x, edge.y) == true) {
    			result=edge.len+result;
    		}	
    	}
    	
    	for(Edge edge:list) {
    		if(union(parent, edge.x, edge.y) == true) {
    			result=edge.len+result;
    		}	
    	}
    	System.out.println("cost归并:"+(System.currentTimeMillis()-time));    	
    	return result;
    	
    }
    
    public int find(int m,int[] parent) {
		while (parent[m] != m) {
			m = parent[m];
		}
		return m;
	}
    
    public boolean union(int[] parent, int index1, int index2) {
    	int m=find(index1,parent);
		int n=find(index2,parent);
		if (m == n) {
			return false;
		}else {
			parent[m] = n;
			return true;
		}
    }
    
}
